<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Thesis">
		<site>mtc-m21b.sid.inpe.br 804</site>
		<holdercode>{isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S}</holdercode>
		<identifier>8JMKD3MGP3W34P/3JG3TF8</identifier>
		<repository>sid.inpe.br/mtc-m21b/2015/05.15.19.04</repository>
		<lastupdate>2015:10.28.17.05.06 sid.inpe.br/mtc-m21b/2013/09.26.14.25.20 administrator</lastupdate>
		<metadatarepository>sid.inpe.br/mtc-m21b/2015/05.15.19.04.58</metadatarepository>
		<metadatalastupdate>2018:06.04.02.55.23 sid.inpe.br/mtc-m21b/2013/09.26.14.25.20 administrator {D 2015}</metadatalastupdate>
		<secondarykey>INPE-17575-TDI/2349</secondarykey>
		<citationkey>Gomes:2015:DiDiDe</citationkey>
		<title>Dispersão discreta e decomposição lagrangeana desbalanceada para o problema de rotulação cartográfica de pontos</title>
		<alternatetitle>Discrete dispersion and unbalanced Lagrangean decomposition for point-feature cartographic labeling problem</alternatetitle>
		<course>CAP-COMP-SPG-INPE-MCTI-GOV-BR</course>
		<year>2015</year>
		<date>2015-05-18</date>
		<thesistype>Tese (Doutorado em Computação Aplicada)</thesistype>
		<secondarytype>TDI</secondarytype>
		<numberofpages>100</numberofpages>
		<numberoffiles>1</numberoffiles>
		<size>1544 KiB</size>
		<author>Gomes, Sóstenes Pereira,</author>
		<committee>Vijaykumar, Nandamudi Lankalapalli (presidente),</committee>
		<committee>Lorena, Luiz Antonio Nogueira (orientador),</committee>
		<committee>Ribeiro, Glaydston Mattos (orientador),</committee>
		<committee>Carvalho, Solon Venâncio de,</committee>
		<committee>Becceneri, José Carlos,</committee>
		<committee>Salles Neto, Luiz Leduíno de,</committee>
		<committee>Marins, Fernando Augusto Silva,</committee>
		<e-mailaddress>sostenes.gomes@gmail.com</e-mailaddress>
		<university>Instituto Nacional de Pesquisas Espaciais (INPE)</university>
		<city>São José dos Campos</city>
		<transferableflag>1</transferableflag>
		<keywords>problema de rotulação cartográfica de pontos, otimização combinatória, dispersão discreta, point-feature labeling problem, combinatorial optimization, discrete dispersion.</keywords>
		<abstract>Este trabalho aborda o Problema de Rotulação Cartográfica de Pontos (PRCP), que é um problema de otimização combinatória, demonstrado na literatura ser NP-difícil. Considera-se que quando todos os pontos devem ser rotulados e sobreposições de rótulos são inevitáveis, o mapa pode ser mais legível se os rótulos em conflito são posicionados de maneira dispersiva, isto é, se os rótulos são posicionados o mais distante possível. Neste contexto, é apresentada uma nova abordagem para o problema, denominada Dispersão Discreta, já utilizada em Problemas de Localização de Facilidades em diversos trabalhos da literatura. Com esta nova abordagem, o PRCP foi formulado como um Problema de programação inteira mista, de maneira a considerar as distâncias entre posições candidatas. Um algoritmo genético construtivo também foi desenvolvido, para obter resultados em instâncias mais complexas. Por fim, é proposta uma Decomposição Lagrangeana desbalanceada, que permitiu obter a solução ótima de diversas instâncias do PRCP, além de provar a otimalidade dos resultados já existentes de outras instâncias. ABSTRACT: This work concerns to the Point-Feature Cartographic Labeling Problem (PFCLP), which is a NP-Hard combinatorial problem. It is considered that when all points must be labeled and overlaps are inevitable, the map can be more readable if overlapping labels are placed in a dispersive way, i. e., overlapping labels are distant from each other. Thus, we present a Discrete Dispersion approach, generally used in the Facility Location Problem, which considers distance values between candidate positions. A constructive genetic algorithm to obtain results in more complex instances is likewise presented. Finally, we propose an unbalanced Lagrangean Decomposition, which achieved the optimal solution of several instances of PFCLP, and proved the optimality of various results of literature.</abstract>
		<area>COMP</area>
		<language>pt</language>
		<targetfile>publicacao.pdf</targetfile>
		<usergroup>administrator</usergroup>
		<usergroup>marcelo.pazos@inpe.br</usergroup>
		<usergroup>sostenes.gomes@gmail.com</usergroup>
		<usergroup>yolanda.souza@mcti.gov.br</usergroup>
		<readergroup>administrator</readergroup>
		<readergroup>marcelo.pazos@inpe.br</readergroup>
		<readergroup>sostenes.gomes@gmail.com</readergroup>
		<readergroup>yolanda.souza@mcti.gov.br</readergroup>
		<visibility>shown</visibility>
		<copyright>urlib.net/www/2012/11.12.15.10</copyright>
		<copyholder>SID/SCD</copyholder>
		<readpermission>allow from all</readpermission>
		<documentstage>not transferred</documentstage>
		<mirrorrepository>sid.inpe.br/mtc-m21b/2013/09.26.14.25.22</mirrorrepository>
		<nexthigherunit>8JMKD3MGPCW/3F2PHGS</nexthigherunit>
		<citingitemlist>sid.inpe.br/bibdigital/2013/10.12.22.16 1</citingitemlist>
		<hostcollection>sid.inpe.br/mtc-m21b/2013/09.26.14.25.20</hostcollection>
		<agreement>autorizacao.pdf .htaccess .htaccess2</agreement>
		<lasthostcollection>sid.inpe.br/mtc-m21b/2013/09.26.14.25.20</lasthostcollection>
		<supervisor>Ribeiro, Glaydston Mattos,</supervisor>
		<supervisor>Lorena, Luiz Antonio Nogueira,</supervisor>
		<url>http://mtc-m21b.sid.inpe.br/rep-/sid.inpe.br/mtc-m21b/2015/05.15.19.04</url>
	</metadata>
</metadatalist>